﻿#pragma once
#include "RBTree.h"
#include <string>
// 模拟STL中，map,set的实现
namespace B
{
	template<class K,class V>
	class map
	{

		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		// 取类里面的内嵌类型 需要使用typename

		typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::const_iterator const_iterator;

		map()
		{}
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		V& operator[](const K& key)
		{
			// V()对应类型的默认构造 
			pair<iterator,bool> ret = _t.Insert(make_pair(key,V()));
			return ret.first->second;
		}

		pair<iterator, bool>  insert(const pair<const K,V>& kv)
		{
			return _t.Insert(kv);
		}


	private:
		RBTree<K, pair<const K, V>,MapKeyOfT> _t;
		// map中 key不能修改，传的时候所以传const K
	};
	void test_map()
	{
		map<int, int> m;
		m.insert(make_pair(1, 1));
		m.insert(make_pair(2, 2));
		m.insert(make_pair(3, 3));

		map<int, int>::iterator it = m.begin();

		while (it != m.end())
		{
			cout << it->first << " " << it->second << " " << endl;;
			// 这个是运算符重载，那么运行的时候直接跑到对应的重载函数内部去执行了
			// 哪里还需要在rb_tree内部再封装一个函数呢？
			// 又不是begin,end这样的，因为它们并不是函数重载啊
			++it;
		}
	}
	void test_map2()
	{
		map<string, string> dict;
		dict.insert(make_pair("string",""));
		dict.insert(make_pair("abc", "a"));
		dict.insert(make_pair("ing", "r"));
		dict.insert(make_pair("str", "h"));

		map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			//it->first = "1111";
			//it->second = "111";
			++it;
		}
		cout << endl;
		for (auto& kv : dict)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
		cout << endl;
	}
	void test_map3()
	{
		string arr[] = { "a","v","a","c","v","e","v","c"};
		map<string, int> cmp;
		for (auto& e : arr)
		{
			cmp[e]++;
		}
		for (auto& kv : cmp)
		{
			cout << kv.first << "：" << kv.second << endl;
		}

	}

}

